package org.uc3m.ed.tad.lista;

import java.util.NoSuchElementException;

/**
 * Implementacion del <B>TAD Lista</B>.
 * 
 * </br></br>
 * 
 * Como implementacion de la lista se toma una <B>lista enlazada utilizando
 * cabecera y centinela</B>. La clase <I>ListaEnlazadaCC</I> proporciona la
 * implementacion de todos los metodos definidos en la interfaz <I>Lista</I>.
 * 
 * @author DEI - ED
 * @version 1.0
 */
public class ListaEnlazadaCC<E> implements ILista<E> {

	/**
	 * Referencia al elemento situado en la primera posicion de la lista.
	 * 
	 * @see ListaEnlazadaNodo<E>
	 */
	private ListaEnlazadaNodo<E> _cabeza;

	/**
	 * Crea una lista.
	 */
	public ListaEnlazadaCC() {

		/*
		 * El nodo que actua como cabecera y la centinela tiene como valor
		 * "null". Por la definicion de la lista, ningun elemento de la
		 * coleccion puede tomar ese valor.
		 */

		_cabeza = new ListaEnlazadaNodo<E>(null);
		_cabeza.asignarSiguiente(_cabeza);
	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see org.uc3m.ed.tad.lista.Lista#estaVacia()
	 */
	public boolean estaVacia() {
		return (_cabeza.obtenerSiguiente() == _cabeza);
	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see org.uc3m.ed.tad.lista.Lista#longitud()
	 */
	public int longitud() {
		int longitud = 0;

		ListaEnlazadaNodo<E> nodo = _cabeza.obtenerSiguiente();
		while (nodo != _cabeza) {
			longitud++;
			nodo = nodo.obtenerSiguiente();
		}

		return longitud;
	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see org.uc3m.ed.tad.lista.Lista#anyadir(java.lang.Object)
	 */
	public boolean anyadir(E elemento) {
		return anyadir(longitud(), elemento);
	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see org.uc3m.ed.tad.lista.Lista#anyadir(int, java.lang.Object)
	 */
	public boolean anyadir(int posicion, E elemento) {
		boolean rc = true;

		// Se busca el elemento.
		int indice = 0;
		ListaEnlazadaNodo<E> nodo = _cabeza.obtenerSiguiente();
		ListaEnlazadaNodo<E> nodoAnterior = _cabeza;
		while ((nodo != _cabeza) && (indice != posicion)) {
			indice++;
			nodoAnterior = nodo;
			nodo = nodo.obtenerSiguiente();
		}

		if (indice != posicion) {
			throw new IndexOutOfBoundsException();
		}

		if (elemento != null) {
			ListaEnlazadaNodo<E> nuevo = new ListaEnlazadaNodo<E>(elemento);
			nuevo.asignarSiguiente(nodo);
			nodoAnterior.asignarSiguiente(nuevo);
			rc = true;
		}

		return rc;
	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see org.uc3m.ed.tad.lista.Lista#eliminar()
	 */
	public void eliminar() {

		// Se asignan a nulo los nodos para facilitar la labor del
		// recolector de memoria.
		ListaEnlazadaNodo<E> nodo = _cabeza.obtenerSiguiente();
		ListaEnlazadaNodo<E> nodoAnterior = _cabeza;
		while (nodo != _cabeza) {
			nodoAnterior = nodo;
			nodo = nodo.obtenerSiguiente();
			nodoAnterior.asignarSiguiente(null);
		}

		// Se eliminan las referencias de la lista.
		_cabeza = null;
	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see org.uc3m.ed.tad.lista.Lista#extraer(java.lang.Object)
	 */
	public boolean extraer(E elemento) {
		boolean rc = true;

		if (estaVacia()) {
			throw new NoSuchElementException();
		}

		// Se busca el elemento.
		int posicion = 0;
		ListaEnlazadaNodo<E> nodo = _cabeza.obtenerSiguiente();
		ListaEnlazadaNodo<E> nodoAnterior = _cabeza;
		while ((nodo != _cabeza) && (!nodo.obtenerElemento().equals(elemento))) {
			posicion++;
			nodoAnterior = nodo;
			nodo = nodo.obtenerSiguiente();
		}

		if (nodo == null) {
			rc = false;
		} else {
			extraer(nodo, nodoAnterior);
			nodo = null;
		}

		return rc;
	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see org.uc3m.ed.tad.lista.Lista#extraer(int)
	 */
	public E extraer(int posicion) {
		E elemento = null;

		if (estaVacia()) {
			throw new NoSuchElementException();
		}

		// Se busca el elemento.
		int indice = 0;
		ListaEnlazadaNodo<E> nodo = _cabeza.obtenerSiguiente();
		ListaEnlazadaNodo<E> nodoAnterior = _cabeza;
		while ((nodo != _cabeza) && (indice != posicion)) {
			indice++;
			nodoAnterior = nodo;
			nodo = nodo.obtenerSiguiente();
		}

		if (nodo == null) {
			throw new IndexOutOfBoundsException();
		} else {
			elemento = extraer(nodo, nodoAnterior);
			nodo = null;
		}

		return elemento;
	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see org.uc3m.ed.tad.lista.Lista#recuperar(int)
	 */
	public E recuperar(int posicion) {
		E elemento = null;

		if (estaVacia()) {
			throw new NoSuchElementException();
		}

		// Se busca el elemento.
		int indice = 0;
		ListaEnlazadaNodo<E> nodo = _cabeza.obtenerSiguiente();
		while ((nodo != _cabeza) && (indice != posicion)) {
			indice++;
			nodo = nodo.obtenerSiguiente();
		}

		if (nodo == null) {
			throw new IndexOutOfBoundsException();
		} else {
			elemento = nodo.obtenerElemento();
		}

		return elemento;
	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see org.uc3m.ed.tad.lista.Lista#obtenerPosicion(java.lang.Object)
	 */
	public int obtenerPosicion(E elemento) {
		int posicion = 0;

		// Se busca el elemento.
		ListaEnlazadaNodo<E> nodo = _cabeza.obtenerSiguiente();
		while ((nodo != _cabeza) && (!nodo.obtenerElemento().equals(elemento))) {
			posicion++;
			nodo = nodo.obtenerSiguiente();
		}

		if (nodo == null) {
			posicion = -1;
		}

		return posicion;
	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see org.uc3m.ed.tad.lista.Lista#sublista(int, int)
	 */
	public ILista<E> sublista(int desde, int hasta) {
		ILista<E> sublista = null;

		if (estaVacia()) {
			throw new NoSuchElementException();
		}

		// Se busca el primer elemento de la lista.
		int indice = 0;
		ListaEnlazadaNodo<E> nodo = _cabeza.obtenerSiguiente();
		while ((nodo != _cabeza) && (indice != desde)) {
			indice++;
			nodo = nodo.obtenerSiguiente();
		}

		if (nodo == null) {
			throw new IndexOutOfBoundsException();
		}

		// Se busca el ultimo elemento de la lista.
		sublista = new ListaEnlazadaCC<E>();
		do {
			sublista.anyadir(nodo.obtenerElemento());
			indice++;
			nodo = nodo.obtenerSiguiente();
		} while ((nodo != _cabeza) && (indice != hasta));

		if (nodo == null) {
			throw new IndexOutOfBoundsException();
		}

		return sublista;
	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see org.uc3m.ed.tad.lista.Lista#iterador()
	 */
	public IListaIterador<E> iterador() {
		return new ListaIterador<E>(this);
	}

	/**
	 * Extrae el dato del primer elemento de la lista.
	 * 
	 * @return Dato del primer elemento, cabeza, de la lista.
	 * @throws NoSuchElementException
	 *             No hay elementos en la lista.
	 */
	E extraerCabeza() {
		E elemento;

		if (estaVacia()) {
			throw new NoSuchElementException();
		}

		ListaEnlazadaNodo<E> nodo = _cabeza.obtenerSiguiente();
		elemento = extraer(nodo, _cabeza);
		nodo = null;

		return elemento;

	}

	/**
	 * Extrae el dato del ultimo elemento de la lista.
	 * 
	 * @return Dato del ultimo elemento, cola, de la lista.
	 * @throws NoSuchElementException
	 *             No hay elementos en la lista.
	 */
	E extraerCola() {
		E elemento;

		if (estaVacia()) {
			throw new NoSuchElementException();
		}

		// Se busca el elemento anterior
		ListaEnlazadaNodo<E> nodo = _cabeza.obtenerSiguiente();
		ListaEnlazadaNodo<E> nodoAnterior = _cabeza;
		while (nodo != _cabeza) {
			nodoAnterior = nodo;
			nodo = nodo.obtenerSiguiente();
		}

		elemento = extraer(nodo, nodoAnterior);
		nodo = null;

		return elemento;
	}

	/**
	 * Recupera, pero no elimina, el dato del primer elemento de la lista.
	 * 
	 * @return Dato del primer elemento, cabeza, de la lista.
	 * @throws NoSuchElementException
	 *             No hay elementos en la lista.
	 */
	E recuperarCabeza() {

		if (estaVacia()) {
			throw new NoSuchElementException();
		}

		return _cabeza.obtenerSiguiente().obtenerElemento();
	}

	/**
	 * Recupera, pero no elimina, el dato del ultimo elemento de la lista.
	 * 
	 * @return Dato del ultimo elemento, cola, de la lista.
	 * @throws NoSuchElementException
	 *             No hay elementos en la lista.
	 */
	E recuperarCola() {
		E elemento;

		if (estaVacia()) {
			throw new NoSuchElementException();
		}

		// Se busca el elemento anterior
		ListaEnlazadaNodo<E> nodo = _cabeza.obtenerSiguiente();
		while (nodo != _cabeza) {
			nodo = nodo.obtenerSiguiente();
		}

		elemento = nodo.obtenerElemento();
		nodo = null;

		return elemento;
	}

	/**
	 * Extrae el valor de un nodo de la lista. Para ello realiza las siguiente
	 * operaciones:
	 * 
	 * <ul>
	 * <li> Reasigna los punteros de la lista para no referenciar al nodo.
	 * <li> Devuelve el valor del nodo.
	 * </ul>
	 * 
	 * @param nodo
	 *            Nodo del elemento a extraer.
	 * @param nodoAnterior
	 *            Nodo anterior al elemento a extraer.
	 * @return Valor del nodo.
	 */
	private E extraer(ListaEnlazadaNodo<E> nodo,
			ListaEnlazadaNodo<E> nodoAnterior) {

		nodoAnterior.asignarSiguiente(nodo.obtenerSiguiente());
		return nodo.obtenerElemento();
	}
}
